#include "get_arg.h"
#include <iostream>
#include <stdlib.h>
#include <sstream>
#include <fstream>
#include <portable_timer.h>
#include <print_error.h>
#include <boost/foreach.hpp>
#include <stlhelper.h>


using namespace std;
using namespace bcpp_matrix;
using boost::lexical_cast;
using std::ostringstream;
using std::istringstream;
using std::ofstream;
using std::ifstream;

/*****************************************************************************************
						merge_unique

******************************************************************************************/
struct t_cnt_strings
{
	string str;
	unsigned cnt;
	t_cnt_strings(const string& s):str(s), cnt(1){}
};
template<typename t_forward_iterator, typename t_binary_predicate, typename t_binary_op>
t_forward_iterator
merge_unique_me(t_forward_iterator first, t_forward_iterator last,
	   t_binary_predicate binary_pred, t_binary_op binary_op)
{
	// Skip the beginning, if already unique.
	first = std::adjacent_find(first, last, binary_pred);
	if (first == last)
		return last;

	// Do the real work.
	t_forward_iterator dest = first;
	++first;
	while (++first != last)
		if (!binary_pred(*dest, *first))
			*++dest = *first;
		else
			binary_op(*dest, *first);
	return ++dest;
}

/*****************************************************************************************
						merge_unique

******************************************************************************************/
template<typename CONT, typename t_binary_predicate, typename t_binary_op>
void merge_unique_me(CONT& container, t_binary_predicate binary_pred, t_binary_op binary_op)
{
	typedef typename CONT::iterator iter;
	iter first = container.begin();
	iter last = container.end();

	// Skip the beginning, if already unique.
	first = std::adjacent_find(first, last, binary_pred);
	if (first == last)
		return;

	// Do the real work.
	iter dest = first;
	++first;
	while (++first != last)
		if (!binary_pred(*dest, *first))
			*++dest = *first;
		else
			binary_op(*dest, *first);
	container.erase(++dest, container.end());
}


struct op_iequal_str : public
std::binary_function<t_cnt_strings, t_cnt_strings, bool>
{
	struct lt_char
	{
		const char* tab;
		lt_char(const char* t) : tab(t) {}
		bool operator()(char x, char y) const {
			return tab[x - CHAR_MIN] == tab[y - CHAR_MIN];
		}
	};
	char tab[CHAR_MAX - CHAR_MIN + 1];
	op_iequal_str(const std::locale& L = std::locale::classic()) {
		const std::ctype<char>& ct
		= std::use_facet<std::ctype<char> >(L);
		for (int i = CHAR_MIN; i <= CHAR_MAX; ++i)
			tab[i - CHAR_MIN] = (char) i;
		ct.toupper(tab, tab + (CHAR_MAX - CHAR_MIN + 1));
	}
	bool operator()(const t_cnt_strings& x,
					const t_cnt_strings& y) const 
	{
		if (x.str.length()  != y.str.length())
			return false;
		return std::equal(x.str.begin(), x.str.end(), y.str.begin(), lt_char(tab));
	}
};  


struct op_iless_str : public
std::binary_function<t_cnt_strings, t_cnt_strings, bool>
{
	struct lt_char
	{
		const char* tab;
		lt_char(const char* t) : tab(t) {}
		bool operator()(char x, char y) const {
			return tab[x - CHAR_MIN] < tab[y - CHAR_MIN];
		}
	};
	char tab[CHAR_MAX - CHAR_MIN + 1];
	op_iless_str(const std::locale& L = std::locale::classic()) {
		const std::ctype<char>& ct
		= std::use_facet<std::ctype<char> >(L);
		for (int i = CHAR_MIN; i <= CHAR_MAX; ++i)
			tab[i - CHAR_MIN] = (char) i;
		ct.toupper(tab, tab + (CHAR_MAX - CHAR_MIN + 1));
	}
	bool operator()(const t_cnt_strings& x,
					const t_cnt_strings& y) const 
	{
		return std::lexicographical_compare(x.str.begin(), x.str.end(), y.str.begin(), y.str.end(), lt_char(tab));
	}
};  


struct op_copy_str_cnt : public
std::binary_function<t_cnt_strings, t_cnt_strings, bool>
{
	void operator()(t_cnt_strings& x,
					t_cnt_strings& y) const 
	{
		x.cnt += y.cnt;
	}
};

struct op_cmp
{
	bool operator()(unsigned i,  unsigned j)
	{return i == j;
	}
};
int main (int argc, char *argv[])
{
	t_program_args args;
	try
	{
		if (!process_command_line_options(argc, argv, args))
			return 1;

		vector<t_cnt_strings> array;
		while (cin)
		{
			string line;
			getline(cin,  line);
			if (line.length())
				array.push_back(t_cnt_strings(line));
		}
		stable_sort(array.begin(),  array.end(),  op_iless_str());
		//array.erase(merge_unique(array.begin(), array.end(), op_iequal_str(),  op_copy_str_cnt()), array.end());
		merge_unique(array, op_iequal_str(),  op_copy_str_cnt());
		BOOST_FOREACH(t_cnt_strings& s, array) 
			cout << s.cnt << "\t" << s.str << std::endl;
	}
	catch(std::exception& e)
	{
		std_print_error(args.CERR(),  e.what());
		return 1;

	}
 




	cerr << "\n";
	cerr << string(10, '!') << "\nEverything worked!!\n";

	std::vector<unsigned> vec;
	vec.push_back(1);
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(4);
	vec.push_back(4);
	BOOST_FOREACH(unsigned i, vec) 
		std::cerr << i << "\n";
	vec.erase(std::unique(vec.begin(),  vec.end(), op_cmp()), vec.end());
	std::cerr << "uniquified\n";
	BOOST_FOREACH(unsigned i, vec) 
		std::cerr << i << "\n";

	return 0;
}


